/**
 * 
 */
package backtrack.passed2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Michael
 * The set [1,2,3,...,n] contains a total of n! unique permutations.
 * By listing and labeling all of the permutations in order,
 * We get the following sequence (ie, for n = 3):
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * Given n and k, return the kth permutation sequence.
 * Note: Given n will be between 1 and 9 inclusive.
 */
public class PermutationSequence {

    public String getPermutation(int n, int k) {
        assert (n >= 1);
        assert (k > 0);
        // generate string for n
        char[] s = new char[n];
        for (int i = 0; i < n; ++i) {
            s[i] = (char) ('0' + i + 1);
        }

        for (int i = 1; i < k; ++i) {
            NextPermutation.nextPermutation(s);
        }

        return new String(s);
    }

    public String getPermutationRecursive(int n, int k) {
        assert (n >= 1);
        assert (k > 0);
        // generate string for n
        char[] s = new char[n];
        for (int i = 0; i < n; ++i) {
            s[i] = (char) ('0' + i + 1);
        }

        for (int i = 1; i < k; ++i) {
            NextPermutation.nextPermutation(s);
        }

        return new String(s);
    }

    int count;
    StringBuffer result = new StringBuffer();

    public String getPermutationRecusive(int n, int k) {
        count = 0;
        if (n == 0 || k == 0) {
            return "";
        }

        StringBuffer sol = new StringBuffer();
        StringBuffer result = new StringBuffer();
        permute(n, k, 1, sol, result);
        //  System.out.println("pass is:" + result);
        String ret = new String(result);
        return ret;
    }

    public void permute(int n, int k, int level, StringBuffer sol,
            StringBuffer result) {
        if (level == n + 1) {
            count++;
            if (count == k) {
                result.append(sol);
            }
        }

        for (int i = level; i <= n; i++) {
            sol.append(i);
            permute(n, k, level + 1, sol, result);
            sol.setLength(sol.length() - 1);
        }

    }
    
    public String getPermutationI0(int n, int k) {
        if (n <= 0 || k <= 0)
            return "";
        
        StringBuilder str = new StringBuilder(n);
        int[] sizes = new int[n + 1];
        sizes[0] = 1;
        for (int i = 1; i <= n; i++) {
            str.append(i);
            sizes[i] = i * sizes[i - 1];
        }
        
        StringBuilder result = new StringBuilder(n);
        int ith = k - 1;
        for (int count = 0; count < n; count++) {
            int size = sizes[str.length() - 1];
            int index = ith / size;
            ith = ith % size;
            result.append(str.subSequence(index, index + 1));
            str.deleteCharAt(index);
        }
        
        return result.toString();
    }

    public String getPermutationI1(int n, int k) {
        if (n <= 0 || k < 1)
            return "";
        
        StringBuffer str = new StringBuffer();
        int[] sizes = new int[n + 1];
        sizes[0] = 1;
        for (int i = 1; i <= n; i++) {
            sizes[i] = i * sizes[i - 1];
            str.append(i);
        }
        if (k > sizes[n])
            return "";

        StringBuffer result = new StringBuffer();
        int i = k - 1;
        while (i >= 0) {
            if (i == 0) {
                result.append(str);
                break;
            }
            int index = k / (sizes[str.length() - 1]);
            k = k % (sizes[str.length() - 1]);
            result.append(str.subSequence(index, index + 1));
            str.deleteCharAt(index);
        }
        return result.toString();
    }

    public String getPermutationI(int n, int k) {
    	if(n == 0)
    		return "";

    	String res = "";

    	// numbers to be added to result string
    	List<Integer> num = new ArrayList<Integer>();

    	// initialization, 0 just for padding
    	for(int i = 0; i <= n; i++)
    		num.add(i);

    	int factorial;
    	int index;

    	for(int i = n; i > 0; i--) {
    		factorial = nFatorial(i - 1);

    		// calculate current number index
    		index = (int) Math.ceil(k / (double) factorial);

    		res += num.get(index);

    		// after adding, delete it from rest set
    		num.remove(index);

    		// update k for the next loop
    		k = k % factorial;
    		if(k == 0)
    			k = factorial;
    	}
    	return res;
    }

    public int nFatorial(int n ) {
    	if(n == 0)
    		return 1;
    	return n * nFatorial(n - 1);
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
    	int i = 2;
    	int r = -3 % 2;
    	System.out.println(r);
//        PermutationSequence ps = new PermutationSequence();
//        for (int i = 1; i <= 6; i++)
//            System.out.println(ps.getPermutationRecusive(3, i));
    }

    /**
     * 
     */
    public PermutationSequence() {
        // TODO Auto-generated constructor stub
    }
}
